def lcs_dp(input_x, input_y):
    # input_y as column, input_x as row
    dp = [([0] * (len(input_y)+1)) for i in range(len(input_x)+1)]
    for i in range(1, len(input_x)+1):
        for j in range(1, len(input_y)+1):
            if i == 0 or j == 0:  # 在边界上，自行+1
                    dp[i][j] = 1
            elif input_x[i-1] == input_y[j-1]:  # 不在边界上，相等就加一
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:  # 不相等
                dp[i][j] = max(dp[i - 1][j], dp[i][j -1])
    intersect_len = dp[-1][-1]
    return intersect_len/min(len(input_x),len(input_y))


def LCS(a, b):
    if a == '' or b == '':
        return ''
    elif a[-1] == b[-1]:
        return LCS(a[:-1], b[:-1]) + a[-1]
    else:
        sol_a = LCS(a[:-1], b)
        sol_b = LCS(a, b[:-1])
        if len(sol_a) > len(sol_b):
            return sol_a
        return sol_b


def LCstr(string1, string2):
    len1 = len(string1)
    len2 = len(string2)
    res = [[0 for i in range(len1 + 1)] for j in range(len2 + 1)]  # python 初始化二维数组 [len1+1],[len2+1]
    result = 0
    index = 0
    for i in range(1, len2 + 1):  # 开始从1开始，到len2+1结束
        for j in range(1, len1 + 1):  # 开始从1开始，到len2+1结束
            if string2[i - 1] == string1[j - 1]:
                res[i][j] = res[i - 1][j - 1] + 1
                if result < res[i][j]:
                    index = i
                result = max(res[i][j], result)
    string = string2[index - result:index]


    return result, string  # 输出


print(LCS("hellooxworld", "aalooxoxp"))

if __name__ == "__main__":
    a = 'hellooxworld'
    b = "aalooxoxp"
    print(LCstr(a, b))